package com.zhzh.sc.demo.leetcode.dp;

/**
 * @author: dasouche
 * @date: 2021-03-10 10:32
 **/
public class lc332 {
    public static int coinChange(int[] A, int M) {
        int[] f = new int[M + 1];
        int n = A.length;
        f[0] = 0;
        int i, j;
        for (i = 1; i <= M; i++) {
            f[i] = Integer.MAX_VALUE;
            for (j = 0; j < n; j++) {
                // 边界条件判断
                if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
                    f[i] = Math.min(f[i - A[j]] + 1, f[i]);
                    System.out.println(i + "=" + f[i]);
                }
            }
        }
        if (f[M] == Integer.MAX_VALUE) {
            f[M] = -1;
        }
        return f[M];
    }

    public static void main(String[] args) {
        int[] xx = new int[]{1, 2, 3};
        int b = 6;
        int i = coinChange(xx, b);
        System.out.println(i);
    }


}
